With regard to embedded devices having large-capacity storage, list fetch is a function that is used frequently in many applications in which such devices are employed, such as car navigation systems, music players, and HDD recorders.
Especially in the case of car navigation systems, a dedicated file system is typically used in which emphasis is placed on real-time processing performance of list fetch operations that use an I/O device that performs seek processing extremely slowly (for example, an I/O device that performs seek processing on CD/DVD storage format) and are implemented so that data to be list-displayed is positioned in sequential space on the disk. However, such a dedicated file system is designed for a device that performs no update operation, and in a case where update is performed using a device capable of update operation (for example, an HDD), the data is rearranged at each update operation.
Further, in a DBMS, as a function to allocate data in sequential space, there is a clustered table that guarantees that data is sorted physically with respect to a specified clustered key column of the table. For example, this shown in Non-Patent Document 1, which is cited herein below.
Here, an example of a conventional embodiment of the clustered table in a DBMS in which storage space management is composed of pages and segments is shown in FIG. 4 and is explained hereinafter.
Here, a page (5002) is a physical unit representing a minimum unit of data I/O to a storage space (5001), and each of segments (5003, 5004) is a physical unit representing a minimum unit for allocation of space in a table and an index. Each segment is composed of a plurality of the pages. The relation between the clustered table and the storage space is shown in FIG. 5. The clustered table (6001) is a clustered table in which a sequential number column (6002) is set as a clustered key column and segments on storage space (6007) are allocated. Rows (6003, 6004, 6005) of the clustered table (6001) are stored in a segment (6014) on the storage space (6007), and another segment (6015) is also allocated to the clustered key column. Thus, in a case where the sequential number column is set as the clustered key column, data is sorted physically with respect to the sequential number column. In segments (6014, 6015), empty space (6012, 6013) is secured for future insert operations.
When an insert operation to the clustered table is performed, since the table is required to maintain a state in which data is sorted physically, insertion is performed by a method different from that for a normal table. A method of performing an insert operation to the clustered table is explained with reference to a flow chart shown in FIG. 6. In the insert processing (7001) for performing the insert operation, first, the size of a row to be inserted and the size of empty spaces of the storage space are compared to make a judgment (7002) of whether the insertion can be performed. Here, if the insertion cannot be performed, an error judgment is made (7012), and the insert processing ends (7009). If the insertion can be performed, a segment including a largest row among rows having a clustered key that is equal or smaller to that of the largest row is searched for in the storage space (7003), and a judgment (7004) of whether there is empty space to insert the row for insertion in the segment is made. If such empty space exists, a procedure A (7013) is carried out. In procedure A, first, a lock of an index related to a corresponding table is obtained (7005), and then, the row is inserted into the empty space in the segment (7006), the index is updated (7007), the lock of the index is released (7008), and the insert processing ends (7009). An operation example in a case where a row having a clustered key of 12 is inserted according to procedure A (7013) is shown in FIG. 7. Here, since there is still empty space (8005) in the segment (8002) that includes a row (8004) having the same clustered key, the row (8006) having the clustered key of 12 is inserted into the empty space in the same segment.
On the other hand, if there is no empty space identified in the judgment (7004) of whether there is empty space to insert the row in the same segment, a procedure B (7014) is carried out. In procedure B, first, a lock of the index related to the corresponding table is obtained (7010), and then, the row is inserted into a new segment (7011), the lock of the index is released (7007), and the insert processing ends (7009). An operation example for a case where a row having a clustered key of 12 is inserted according to procedure B (8014) is shown in FIG. 8. Here, since there is no empty space in the segment (9002) that includes a row (9004) having the same clustered key, a new segment (9005) is secured and the row (9006) having the clustered key of 12 is inserted is the new segment.
Since storage I/O is sequentialized, the search speed improves through use of the clustered table in performing a search with a designated range of the clustered key value. However, a state in which data is sorted physically is broken by update and insert operations over space that was empty when the table was prepared, and therefore, periodic maintenance is required. This maintenance involves rearrangement of all data in the same manner as in the update operation for the dedicated file system described above.
In a DBMS used for an embedded application, to achieve data I/O performance comparable to that of a dedicated file system that performs no update operations, it is necessary to arrange data in physical sequential space in the same manner as the conventional system described above. However, in the embedded application, since long-term, maintenance-free performance and stability is important, the conventional clustered table cannot be used. Therefore, a table structure that is specialized for data fetch of a pattern called using list fetch in such an embedded application and improving I/O performance is desired.
Characteristics of the list fetch operation will now be explained with reference to FIG. 9 using a car navigation application as an example. In the car navigation system, intersection data is handled in units of map information. The intersection data is divided into sections (10001) each having a unique identifier and individually managed. In the car navigation application, real-time processing performance of list fetch operations of the intersection data is of primary importance. Such a list fetch is performed in a route search in the present example in the following two patterns:
1. List fetch of intersections in a section (10002) that includes the car in which the a car navigation application is being used; and
2. list fetch of intersections in the section (10002) that includes the car in which the a car navigation application is being used and the 8 adjacent sections (10003).
Here, a pattern in which all data is arranged in sequential space in a case of a file system dedicated for car navigation is used as the pattern of 1, and in which it is impossible to arrange all data including the pattern 2 in the sequential space. Therefore, also in a DBMS specialized for an embedded application, it is sufficient to guarantee that the pattern 1 is arranged in the sequential space.
Also, as a characteristic common to the two patterns, it is noted that a search condition uses an equality condition of a section number and that a plurality of intersections having the same section number exist in search target data. By formulating this characteristic in terms of a DBMS, it becomes a search of an equality condition with respect to columns that include a duplicated key.
It is further noted that similar list fetch operations also appear frequently in applications other than the car navigation application discussed above. For example, list fetch operations such as “list of music titles by an identical artist” and “list of music titles contained in an identical album” in music player applications, as well as “list of programs of a specified month and day” and “list of programs of a specified channel” in HDD recorder applications, frequently appear.
Non-Patent Document 1: [Product Manual] Scalable Database Server HiRDB Version 7 System Introduction and Design Guide (For UNIX®) 3000-6-272, 12.9 Specification of Clustered Key”, pp. 342-343.